import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/25 15:08
 * @description 动态规划
 */
public class Solution {
    public static void main(String[] args) {

    }
    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length(), m = s2.length(), t = s3.length();

        if (n + m != t) {
            return false;
        }
        // 定义f[i][j] 表示s1的前i个元素和 s2的前j个元素能够交错组成 s3的前 i + j 个元素
        boolean[][] f = new boolean[n + 1][m + 1];
        // 边界条件，f[0][0] 空字符串能够交错组成空字符串，为 true
        f[0][0] = true;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                int p = i + j - 1;
                if (i > 0) {
                    // 如果f[i-1][j] 并且 s1.charAt(i-1) = s3.chartAt(p) 那么能递归
                    f[i][j] = f[i][j] || (f[i - 1][j] && s1.charAt(i - 1) == s3.charAt(p));
                }
                if (j > 0) {
                    f[i][j] = f[i][j] || (f[i][j - 1] && s2.charAt(j - 1) == s3.charAt(p));
                }
            }
        }

        return f[n][m];

    }
}
